package lcof;

import pojo.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class TreeGroup {


    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //打表记录中序遍历的元素值和下标
        Map<Integer, Integer> map = new HashMap();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        //参数：前序遍历左右子树边界，根为左边界
        //参数：前序遍历左右子树边界，根为map寻址
        return recur(map, preorder, inorder, 0, preorder.length - 1, 0, preorder.length - 1);
    }

    public TreeNode recur(Map<Integer, Integer> map, int[] preorder, int[] inorder, int preLeft, int preRight, int inLeft, int inRight) {
        //1.判断数组合法性
        if (preLeft > preRight) {
            return null;
        }
        //1.当前根节点
        TreeNode root = new TreeNode(preorder[preLeft]);
        //2.找到中序遍历的根节点下标
        Integer inIndex = map.get(root.val);
        //3.划分下次的左右子树
        //3.1计算下次左子树长度
        int length = inIndex - 1 - inLeft;
        //3.2 左子树
        root.left = recur(map, preorder, inorder, preLeft + 1, preLeft + 1 + length, inLeft, inIndex - 1);
        root.right= recur(map, preorder, inorder, preLeft + 1 + length + 1, preRight, inIndex + 1, inRight);
        return root;
    }


    public TreeNode buildTree2(int[] inorder, int[] postorder) {
        // [[left],r,[right] ]
        // [[left],[right],r ]
        //打表记录中序遍历的元素值和下标
        Map<Integer, Integer> map = new HashMap();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return recur2(map, postorder, 0, postorder.length - 1, 0, inorder.length - 1);
    }

    public TreeNode recur2(Map<Integer, Integer> map, int[] postorder, int PL, int PR, int IL, int IR) {
        //合法性
        if (PL > PR) {
            return null;
        }
        //1.根节点
        TreeNode root = new TreeNode(postorder[PR]);
        //2.中序遍历下标
        Integer index = map.get(root.val);
        //3.右子树长度
        int len = IR - index ;
        //4.再次递归
        //右
        root.right= recur2(map, postorder, PR - len, PR - 1, index + 1, IR);
        //左
        root.left= recur2(map, postorder, PL, PR - len - 1, IL, index - 1);
        return root;
    }

















    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        //pre  [root,[left],[right]]
        //post [[left],[right],root]
        //预处理后续遍历map
         Map<Integer,Integer> map= new HashMap();
        for (int i = 0; i < postorder.length; i++) {
            map.put(postorder[i], i);
        }
        return recur3(map, preorder, postorder, 0, preorder.length-1, 0, postorder.length-1);
    }

    public TreeNode recur3(Map<Integer, Integer> map, int[] preorder, int[] backorder, int PL, int PR, int BL, int BR) {
        //合法性
        if (PL > PR) {
            return null;
        }
        //前序遍历PL[0]为根
        TreeNode root = new TreeNode(preorder[PL]);
        //划分下次遍历区间
        //1.找到后序遍历的根节点下标
        Integer index = map.get(root.val);
        //2.下次的左节点root为PL+1，但是注意边界
        if (PL + 1 > PR) {
            return root;
        }
        int nextLeftRoot = preorder[PL + 1];
        //寻找下标
        Integer nextIndex = map.get(nextLeftRoot);
        //区间长度
        int left = nextIndex - BL + 1;
        int right = index - nextIndex - 1;
        //递归
        root.left =  recur3(map, preorder, backorder, PL + 1, PL + left, BL, nextIndex);
        root.right = recur3(map, preorder, backorder, PL + left + 1, PL + left + right, nextIndex + 1, index-1);//3,2,
        return root;
    }






}
